package DP_718;

public class Solution {
	public int findLength(int[] A, int[] B) {
		return dp(A,B);
//		return SW(A, B);

	}

	private int SW(int[] A, int[] B) {
		int n = A.length, m = B.length;
		int ret = 0;
		for (int i = 0; i < n; i++) {
			int len = Math.min(m, n - i);
			int maxlen = maxLength(A, B, i, 0, len);
			ret = Math.max(ret, maxlen);
		}

		for (int i = 0; i < m; i++) {
			int len = Math.min(n, m - i);
			int maxlen = maxLength(A, B, 0, i, len);
			ret = Math.max(ret, maxlen);
		}
		return ret;
	}

	private int maxLength(int[] A, int[] B, int addA, int addB, int len) {
		int ret = 0, k = 0;
		for (int i = 0; i < len; i++) {
			if (A[addA + i] == B[addB + i]) {
				k++;
			} else {
				k = 0;
			}
			ret = Math.max(ret, k);
		}
		return ret;
	}

	private int dp(int[] A, int[] B) {
		int n = A.length, m = B.length;
		int ans = 0;
		int[][] dp = new int[n + 1][m + 1];
		for (int i = n - 1; i >= 0; i--) {
			for (int j = m - 1; j >= 0; j--) {
				dp[i][j] = A[i] == B[j] ? dp[i + 1][j + 1] + 1 : 0;
				ans = Math.max(ans, dp[i][j]);
			}
		}

		return ans;
	}
}
